package linkedlist.other;

import linkedlist.Node;

/**
 * @Author wangtengyu
 * @Create 2018-09-11-9:18
 *
 * 找链表中环的入口节点 1.快慢指针，判断有没有环 2.有环的话，快慢指针相遇的，走一圈，回到这个节点，求出环的节点的数量n 3.定义两个指针指向头结点，第一个指针先走n步，然后第二个指针开始走，两个指针相遇的节点即入口节点
 */
public class FindCircuitStartNode {


  public Node findStart(Node head) {
    if (head == null) {
      throw new RuntimeException("传入的节点为空");
    }

    int count = isCircuit(head);
    if (count == 0) {
      return null;
    }

    Node p1 = head;
    Node p2 = head;
    while (count > 0) {
      p2 = p2.getNext();
      count--;
    }

    while (p1 != p2) {
      p1 = p1.getNext();
      p2 = p2.getNext();
    }
    return p1;
  }


  /**
   * 判断是否是环路 如果是环路，返回环路中节点个数， 如果不是环路，返回-1
   */
  public int isCircuit(Node head) {
    int num = 0;
    if (head == null) {
      return 0;
    }

    Node slow = head;
    Node fast = head;
    while (fast.getNext().getNext() != null) { //快指针的下一个为null，说明没有环路
      slow = slow.getNext();
      fast = fast.getNext().getNext();
      if (slow == fast) {
        num = getCount(slow, fast);
        break;
      }
    }
    return num;
  }

  /**
   * 找到环路中的节点数量
   */
  private int getCount(Node slow, Node fast) {
    int count = 0;
    if (slow == null || fast == null) {
      return 0;
    }

    Node head = slow;
    while (true) {
      slow = slow.getNext();
      count++;
      if (slow == head) {
        break;
      }
    }
//        Node head=slow;
//        slow=slow.getNext();
//        count++;
//        while (slow!=head){
//            slow=slow.getNext();
//            count++;
//        }
    return count;
  }


  public static void main(String[] args) {
    FindCircuitStartNode findCircuitStartNode = new FindCircuitStartNode();
    Node node1 = new Node(1);
    Node node2 = new Node(2);
    Node node3 = new Node(3);
    Node node4 = new Node(4);
    Node node5 = new Node(5);
    Node node6 = new Node(6);
    node1.setNext(node2);
    node2.setNext(node3);
    node3.setNext(node4);
    node4.setNext(node5);
    node5.setNext(node6);
    node6.setNext(node1);
    Node startNode = findCircuitStartNode.findStart(node1);
    if (startNode != null) {
      System.out.println("环路的初始节点是" + startNode.getData());
      System.out.println("环路中的节点数量" + findCircuitStartNode.isCircuit(node1));
    } else {
      System.out.println("链表中不存在环路");
    }
  }


}
